/*
 * greedy.c
 *
 *  Created on: 17 sept. 2013
 *      Author: the
 */
#include"greedy.h"
#define DEBUGANH 0
int verifieContrainte(int id)
{
	int i, idNgh;

	//Verification des contraintes : si le noeud id ou id2 n'ont pas de voisinage avec la fréquence 'freq'
	for(i=0;i<nodes[id].nbN1;i++)
	{
		idNgh=nodes[id].N1[i].id;
		if(linkExist2(id,idNgh)==0){
			//fprintf(stderr,"-- pas connecte %i <--> %i (%f,%f) (%f,%f) %i-%i\n",id,idNgh,nodes[id].x,nodes[id].y,nodes[idNgh].x,nodes[idNgh].y,nodes[id].frequency[0],nodes[idNgh].frequency[0]);
//			printf("Contrainte 1 \n");
			return(0);
		}
	}


	// Verification des contraintes : Si l'on a le nombre de fréquence qui est supérieur au nombre de radio
	int compte = 0;
	for(i = 0 ; i < maxFreq ; i ++)
		if( usedfreq (id,i) != -1)
			compte++;

	if( compte > nbOfRadios)
	{
//		printf("Contrainte 2 \n");
		return 0;
	}

	// Verification des contraintes : Si l'on a des fréquences différentes sur la même radio
	int id2,id3;
	for(id2=0;id2<nodes[id].nbN1;id2++)
	{
	//	int voisi1 = nodes[id].N1[id2].id;
		int radio1 = nodes[id].N1[id2].radio;
		int freq1 = nodes[id].N1[id2].frequency;

		for(id3=id2+1;id3 < nodes[id].nbN1;id3++)
		{
//			int voisi2 = nodes[id].N1[id3].id;
			int radio2 = nodes[id].N1[id3].radio;
			int freq2 = nodes[id].N1[id3].frequency;

			if(radio1==radio2 && freq1!=freq2)
			{
//				printf("Contrainte 3 \n");
				return 0;
			}
		}
	}


	return(1);
}

//int trouverFreq(int radioId, int radioId2, int oldFreqId, int id, int oldFreqId2, int id2, int freq, int conflict, int minConflict,
//		          int* bestFreq, int* bestRadioId, int* bestRadioId2)
int trouverFreq(int id,int id2,int minConflict,int* bestFreq, int* bestRadioId, int* bestRadioId2)
{

	int radioId,radioId2,oldFreqId, oldFreqId2, freq, conflict;

	int indexId = getIndexN1(nodes[id2],id);
	int indexId2 = getIndexN1(nodes[id],id2);


	*bestRadioId = nodes[id].N1[indexId2].radio;
	*bestRadioId2 = nodes[id2].N1[indexId].radio;
	*bestFreq = nodes[id].N1[indexId2].frequency;

	//On parcours les radios du noeud id
	for (radioId = 0;radioId < nbOfRadios;radioId++)
	{
		//On parcours les radios du noeud id2
		for (radioId2 = 0; radioId2 < nbOfRadios; radioId2++)
		{

			//On memorise l'ancienne assignation (pour pouvoir la remettre ensuite)
			oldFreqId = nodes[id].frequency[radioId];
			oldFreqId2 = nodes[id2].frequency[radioId2];

			//On alloue toutes les frequences possibles a ces deux radios/lien
			for (freq = 0; freq < maxFreq; freq++)
			{

				//Assignation
				nodes[id].N1[indexId2].radio = radioId;
				nodes[id].N1[indexId2].frequency = freq;
				nodes[id].frequency[radioId] = freq;

				nodes[id2].N1[indexId].radio=radioId2;
				nodes[id2].N1[indexId].frequency=freq;
				nodes[id2].frequency[radioId2] = freq;

//				printf("[node:%d radioId:%d ;oldFreqId:%d] [node:%d radioId2:%d ;oldFreqId2:%d ] : freq:%d \n",
//								 id,radioId,oldFreqId,id2,radioId2,oldFreqId2,freq);

	///			if(id==4 && radioId==1 && oldFreqId==2 && id2==1 && radioId2==1 && oldFreqId2==1)
	//			{
	//				printf("GO \n");
	//			}

				//Verification des contraintes : si le noeud id ou id2 n'ont pas de voisinage avec la fréquence 'freq'
				if ((verifieContrainte(id) == 0) || (verifieContrainte(id2) == 0))
				{
					//Retour a l'assignation initiale
					nodes[id].N1[indexId2].radio = radioId;
					nodes[id].N1[indexId2].frequency=oldFreqId;
					nodes[id].frequency[radioId] = oldFreqId;

					nodes[id2].N1[indexId].radio = radioId2;
					nodes[id2].N1[indexId].frequency = oldFreqId2;
					nodes[id2].frequency[radioId2] = oldFreqId2;

					continue;
				}
				//On regarde si l'assignation est meilleure - si oui on la memorise
				conflict = calculConflictGraphGreedy(); //conflictGraphGreedy(0);

	//			printf("conflict:%d minconflict:%d \n",conflict,minConflict);
				if (conflict < minConflict)
				{
					*bestFreq = freq;
					*bestRadioId = radioId;
					*bestRadioId2 = radioId2;
					minConflict = conflict;
				}
				//Retour a l'assignation initiale
				nodes[id].N1[indexId2].radio = radioId;
				nodes[id].N1[indexId2].frequency=oldFreqId;
				nodes[id].frequency[radioId] = oldFreqId;


				nodes[id2].N1[indexId].radio = radioId2;
				nodes[id2].N1[indexId].frequency = oldFreqId2;
				nodes[id2].frequency[radioId2] = oldFreqId2;
			}
			//fin du for sur freq}
			//fin du for sur radioId2}
			//fin du for sur Idreturn minConflict;
		}
	}

	//Retour a l'assignation initiale
	nodes[id].N1[indexId2].radio = *bestRadioId;
	nodes[id].N1[indexId2].frequency=*bestFreq;
	nodes[id].frequency[*bestRadioId] = *bestFreq;


	nodes[id2].N1[indexId].radio = *bestRadioId2;
	nodes[id2].N1[indexId].frequency = *bestFreq;
	nodes[id2].frequency[*bestRadioId2] = *bestFreq;


	return minConflict;
}

//Alloue une frequence à la radioème radio du noeud id avec le voisin id2.
int allocateGreedy(int id, int id2)
{
//	int radioId, freq, oldFreqId, oldFreqId2, radioId2, conflict, minConflict, oldConflict;
	int bestFreq , bestRadioId , bestRadioId2 ;

	//La ligne du dessous calcule la somme des graphes des conflits pour toutes les frequences
	int oldConflict= calculConflictGraphGreedy(); //conflictGraphGreedy(0);
	int minConflict=oldConflict;

//	if ( (id==0 && id2 ==3) || (id==3 && id2 ==0) )
//	{
//		printf("GO \n");
//	}
//	printf("***** link(%d,%d) ********\n",id,id2);

//	affichageConflictReseaux();


	//On parcours les radios du noeud id
//	minConflict = trouverFreq(radioId, radioId2, oldFreqId, id,
//			oldFreqId2, id2, freq, conflict, minConflict,
//			&bestFreq,&bestRadioId, &bestRadioId2);

	minConflict = trouverFreq(id,id2,minConflict,&bestFreq,&bestRadioId, &bestRadioId2);




//	printf("[node:%d radio:%d freq:%d] [node:%d radio:%d freq:%d] \n",id,bestRadioId,bestFreq,id2,bestRadioId2,bestFreq);


	//Il n'y a pas d'amelioration possible pour ce lien
	if(oldConflict==minConflict)
	{
		return(0);
	}

/*
	//Sinon on effectue l'assignation
	nodes[id].frequency[bestRadioId]=bestFreq;
	nodes[id2].frequency[bestRadioId2]=bestFreq;

	//On met aussi a jour les infos sur le lien et sur les noeuds --> frequence et radio a utilise.
	//Attention cette partie la doit aussi se trouver dans les autres algorithmes d'allocation car utilise pour fixer les routes statiques.
	if((index=getIndexN1(nodes[id],id2))<0)
		fprintf(stderr,"Error greedy.c: index not found\n");

	nodes[id].N1[index].frequency=bestFreq;
	nodes[id].N1[index].radio=bestRadioId;

	if((index=getIndexN1(nodes[id2],id))<0)
		fprintf(stderr,"Error greedy.c: index not found\n");

	nodes[id2].N1[index].frequency=bestFreq;
	nodes[id2].N1[index].radio=bestRadioId2;
*/

//	affichageConflictReseaux();

	return(1);
}//End of the function allocateGreedy();


//Compute the conflict graph for a link bidirectional with a conflict at 3 hops.
int conflictGraphLink4(int id1, int id2, int frequency)
{
	   int i, j, idN1, idN2, idN3, conflict=0;

	    // si id1 et id2 ne sont pas de voisin
	    if(isNeighbor(id1,id2)==0)
	    	return -1;

		// The Anh : ne compte pas le lien sans frequence
		if( VIDE==frequency)
			return -1;

	    /////////////////////////////////////
	    //  Traitement auprès du noeud id1 //
	    /////////////////////////////////////
		for(i=0;i<nodes[id1].nbN1;i++)
		{
			idN1=nodes[id1].N1[i].id;//index of the neighbor

			//direct neighbor
			if( linkUsedFrequency(id1,idN1,frequency) && (idN1!=id2)){
				conflict++;
//				if(DEBUGANH) printf("link (%d,%d) in conflict-1: %d\n",id1,idN1,conflict);
			}

			//2 1-neighbors together
			for(j=i+1;j<nodes[id1].nbN1;j++){
				if(linkUsedFrequency(idN1,nodes[id1].N1[j].id,frequency)==1){
					conflict++;
//					if(DEBUGANH) printf("link (%d,%d) in conflict-2; %d\n",idN1,nodes[id1].N1[j].id,conflict);
				}
			}

			//neighbor with 2-neighbors
			for(j=0;j<nodes[id1].nbN2;j++){
				if(linkUsedFrequency(idN1,nodes[id1].N2[j].id,frequency)==1){
					conflict++;
//					if(DEBUGANH) printf("link (%d,%d) in conflict-3; %d \n",idN1,nodes[id1].N2[j].id,conflict);
				}
			}

		}

		//2 2-neighbors together
		for(i=0;i<nodes[id1].nbN2;i++)
		{
			idN2 = nodes[id1].N2[i].id;//index of the neighbor
			for(j=i+1;j<nodes[id1].nbN2;j++)
			{
				if(linkUsedFrequency(idN2,nodes[id1].N2[j].id,frequency)==1)
				{
					conflict++;
//					if(DEBUGANH) printf("link (%d,%d) in conflict-4; %d\n",idN2,nodes[id1].N2[j].id,conflict);
				}
			}
		}

		//neighbor with 3-neighbors of node id1
		for(i=0;i<nodes[id1].nbN2;i++)
		{
			idN2 = nodes[id1].N2[i].id;
			for(j = 0 ; j < nodes[idN2].nbN1;j++)
			{
				idN3 = nodes[idN2].N1[j].id;

				if( is3Neighbor(idN3,id1) && (linkUsedFrequency(idN2,idN3,frequency)==1) )
				{
					conflict++;
//					if(DEBUGANH) printf("link (%d,%d) in conflict-5 ; %d\n",idN2,idN3,conflict);
				}
			}
		}


		   /////////////////////////////////////
		   //  Traitement auprès du noeud id2 //
		   /////////////////////////////////////

			//2 2-neighbors together
			for(i=0;i<nodes[id2].nbN2;i++)
			{
				idN2 = nodes[id2].N2[i].id;//index of the neighbor
				for(j=i+1;j<nodes[id2].nbN2;j++)
				{
					if(linkUsedFrequency(idN2,nodes[id2].N2[j].id,frequency)==1)
					{
						conflict++;
//						if(DEBUGANH) printf("link (%d,%d) in conflict-6; %d\n",idN2,nodes[id2].N2[j].id,conflict);
					}
				}
			}

	      // 3-neighbors of node id2
			for(i = 0 ; i < nodes[id2].nbN2;i++)
			{
				idN2 = nodes[id2].N2[i].id;
				for(j = 0 ; j < nodes[idN2].nbN1;j++)
				{
					idN3 = nodes[idN2].N1[j].id;

					// idN3 est le voisinage 3-sauts de id2
					if( linkUsedFrequency(idN2,idN3,frequency)==1 && (is3Neighbor(idN3,id2)==1)
					 && (isNeighbor(id1,idN3)==0) && (is2Neighbor(id1,idN3)==0) && (is3Neighbor(id1,idN3)==0))  // et idN3 n'est pas de voisinage 1,2,3 saut de id1
					{
						conflict ++;
//						if(DEBUGANH) printf("link (%d,%d) in conflict-7 ; %d  \n",idN2,idN3,conflict);
					}
				}
			}


//			if(DEBUGANH)   printf("Conflict link (%d,%d) = %d\n",id1,id2,conflict);
		return conflict;

}

//Compute the conflict graph
int calculConflictGraphGreedy()
{
	int conflict = 0;

	int id,id2;
	for(id=0;id<nbOfNodes;id++)
	{
    	for(id2=0;id2<nodes[id].nbN1;id2++)
    	{
    		if(nodes[id].N1[id2].frequency != VIDE)
    		{
    			// récuperer index
				int frequence = nodes[id].N1[id2].frequency;
				conflict += conflictGraphLink4 (id,nodes[id].N1[id2].id,frequence);

    		}
    	}
	}

	conflict = conflict / 2;

	return conflict;
}

void affichageConflictReseaux()
{
	fprintf(stderr,"\n");

	fprintf(stderr,"Conflict Reseaux en cours:%d \n",calculConflictGraphGreedy());
		int id,id2;
		for(id=0;id<nbOfNodes;id++)
	    	for(id2=0;id2<nodes[id].nbN1;id2++)
	    		if(nodes[id].N1[id2].frequency > -1)
	    		{
	    			// récuperer index
	    			int frequence = nodes[id].N1[id2].frequency;

	    			fprintf(stderr,"-Link (%d, %d) radio=%d freq=%d Debit:%d Conflict=%d\n",
							  id,nodes[id].N1[id2].id,nodes[id].N1[id2].radio,
							  nodes[id].N1[id2].frequency,getMetric(id,nodes[id].N1[id2].id),
							  conflictGraphLink4 (id,nodes[id].N1[id2].id,frequence));

	    		}

		fprintf(stderr,"\n");
}

//Allocate the frequency to the nodes
void allocateFrequencyGreedy(int nbOfRoutes)
{
	int iteration=0, resultat, id, index, id2, maxIter, radio, j;
	double maxCapacite=0.0;

	//On assigne une frequence commune (mais a jour aussi les couples radio et interface a utiliser pour atteindre un voisin).
	//Important car tous les liens ne seront pas visites par l'algo

	// THe ANH
	//	allocateSameFrequency(nbOfRoutes);

	  //On assigne toutes les radios de tous les noeuds sur la freq 0
	    for(id=0;id<nbOfNodes;id++)
		{
			nodes[id].frequency[0]=0;

			//On fixe les radios/freq vers les voisins a (0,0)
	    		for(j=0;j<nodes[id].nbN1;j++)
	    		{
	    			nodes[id].N1[j].frequency=0;
	    			nodes[id].N1[j].radio=0;
	    		}
		}

	// Fin THe ANh



	//On assigne les autres radios de tous les noeuds sur la freq 0
	for(id=0;id<nbOfNodes;id++)
		for(radio=1;radio<nbOfRadios;radio++)//La radio 0 c'est deja fait
			nodes[id].frequency[radio]=0;

	//On fixe ici le nombre d'iterations maximum sans ameloriation
	maxIter=nbOfNodes*nbOfNodes*20;

//	affichageConflictReseaux();

	while(iteration<maxIter)
   	{
			//On tire au hasard un noeud
    		id=(int) (1.0 * (nbOfNodes-1) * (rand() / (RAND_MAX + 1.0)));

    		//On tire un de ces voisins au hasard
    		index=(int) (1.0 * (nodes[id].nbN1-1) * (rand() / (RAND_MAX + 1.0)));
    		id2=nodes[id].N1[index].id;

			//On effectue une allocation pour le lien (id,id2)
			resultat=allocateGreedy(id,id2);


			if(resultat)
			{
				iteration=0;

//			    printf("conflict = %d\n",calculConflictGraphGreedy());
		//	    affichageConflictReseaux();

			}
			else
				iteration++;



   	}

   	 for(j=0;j<nbOfRoutes;j++)
     {
         if(nodes[0].routingTable[j].destination>=0 && nodes[0].routingTable[j].nextHop>=0)
         {
         	nodes[0].routingTable[j].cost=getMetric(0,nodes[0].routingTable[j].nextHop);
        	nodes[0].routingTable[j].cost2=calculMinCapaciteChemin(j);
        	maxCapacite+=nodes[0].routingTable[j].cost2;
         }
      }
   	 fprintf(stderr,"maxCapacite(Greedy)=%f\n",maxCapacite);
     affichageConflictReseaux();

 //     affichageReseau();


}//End of the function allocateFrequencyGreedy();


